mod merge;
mod insert;
mod select;
mod quick;

fn swap(a: & mut Vec<i32>, i: usize, j: usize) {
    if i == j {
        return
    }

    let t = a[i];
    a[i] = a[j];
    a[j] = t;

}

fn part(a: & mut Vec<i32>, start:usize, end:usize) -> usize{
    let p = a[start]; 
    let mut i = start + 1;
    let mut j = end;

    // 整个过程是从两侧向中间靠拢，逐渐缩小无序区间的大小。

    // i 指向可以被占用的位置。
    loop {
        // 相遇时退出循环。
        // 相等时，i可能是满足<p的要求，所以要再向后找一个。
        if i > j {
            break
        }

        // 说明[start, i]是有序的。i可以自增。
        if p >= a[i] {
            i += 1;
            continue
        }

        // 说明[j, end]是有序的，可以自减1。
        if p <= a[j] {
            j -= 1;
            continue;
        }

        // 刚好相反，时交换，保证两边都有序的不变式。
        if p < a[i] && p > a[j] {
            swap(a, i, j);
        }
    }
    // i-1是最右侧小于p的。
    swap(a, start, i-1);
    return i-1;
}

fn sort(a: & mut Vec<i32>, start:usize, end:usize) {
    if start >= end {
        return
    }

    let p = part(a, start, end);

    // 判断大于0时，才能对前半段做排序，usize不能取值-1。
    if p > 0 {
        sort(a, start, p - 1);
    }
    sort(a, p + 1, end);
}

fn quick(a: & mut Vec<i32>) {
    sort(a, 0, a.len() - 1);
}

fn main() {
    let mut a = vec![2, 5, 3, 8, 4, 19, 30, 35];
    quick(&mut a);
    // let l = a.len();
   //  part(&mut a, 0, l - 1);
    println!("{:?}", a);

    a = vec![32, 5, 3, 8, 4, 19, 30, 35, 100, 32];
    quick(&mut a);
    println!("{:?}", a);

    a = vec![32, 10];
    quick(&mut a);
    println!("{:?}", a);

    a = vec![10, 32, 50];
    quick(&mut a);
    println!("{:?}", a);
}
